#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
// 438. 找到字符串中所有字母异位词【中等】
// 给定一个字符串s和一个非空字符串p，找出s中的所有p的anagrams的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
// s 和 p 仅包含小写字母
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.size() < p.size())
            return res;
        assert(p.size() > 0);

        vector<int> freq_p(26,0);   // 记录p中字符的频率
        for(char c: p)
            freq_p[c - 'a'] += 1;

        vector<int> freq_s(26, 0);  // 记录s中字符的频率
        // 定义s中的滑动窗口
        int l = 0, r = -1;  // 滑动窗口： s[l, r]
        while(r+1 < s.size()) {
            r ++;   // 向右拓展窗口
            freq_s[s[r] - 'a']++;
            if(r - l + 1 > p.size())
                freq_s[s[l++] - 'a']--; // 向左移动一位

            if(r - l + 1 == p.size() && same(freq_s, freq_p))
                res.push_back(l);
        }
        return res;
    }

private:
    bool same(const vector<int>& freq_s, const vector<int>& freq_p) {
        for(int i = 0; i < 26; i++)
            if(freq_s[i] != freq_p[i])
                return false;
        return true;
    }
};

void printVec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {
    string s1 = "cbaebabacd";
    string p1 = "abc";
    printVec(Solution().findAnagrams(s1, p1));
    // [0, 6]
    string s2 = "abab";
    string p2 = "ab";
    printVec(Solution().findAnagrams(s2, p2));
    return 0;
}
